package cn.fxzhang.leetcode.no00;

import java.util.*;

/**
 * 90. 子集 II
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 * nums = [1,2,2]
 * [[],[1],[1,2],[1,2,2],[2],[2,2]]
 * 1 <= nums.length <= 10
 * -10 <= nums[i] <= 10
 *
 * 类型：穷举/搜索
 * 题解：每个数字可以取0次到多次，按序取数即可
 * 时间复杂度：O(n * 2^n), 一共 2^n个状态，每种状态需要 O(n)的时间来构造子集
 * 空间复杂度：O(n), 即构造子集使用的临时数组 subset 的空间代价
 *
 * 提交记录(1/1)：
 * 执行用时: 3 ms, 击败了24.13%
 * 内存消耗: 38.7 MB, 击败了60.16%
 *
 * 【中等】通过次数79,797提交次数127,509
 * @author 张晓帆
 * @date 2021/3/31
 */
public class P0090_Subsets_Ii {

    List<List<Integer>> result = new ArrayList<>();;
    List<Integer> subset= new ArrayList<>();;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<Integer> distinctNums = new ArrayList<>();
        Arrays.sort(nums);
        // 去重和统计次数
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            Integer count = countMap.get(num);
            if (count == null){
                countMap.put(num, 1);
                distinctNums.add(num);
            } else {
                countMap.put(num, count+1);
            }
        }
        Collections.reverse(distinctNums);
        search(distinctNums, countMap, 0);
        return result;
    }

    /**
     *
     * @param nums 不重复的数字
     * @param countMap 数字出现次数
     * @param n 准备取第几个数字
     */
    private void search(List<Integer> nums, Map<Integer, Integer> countMap,  int n) {
        if (n >= nums.size()){
            result.add(new ArrayList<>(subset));
            return;
        }
        // 当前数字
        Integer num = nums.get(n);
        // 当前数字可取次数
        Integer count = countMap.get(num);
        for (int i = 0; i <= count; i ++){
            for (int j = 0; j < i; j++){
                subset.add(num);
            }
            search( nums, countMap, n+1);
            for (int j = 0; j < i; j++){
                subset.remove(subset.size()-1);
            }
        }
    }
}
